package Demo01;

public class Main {
}

class Solution {
    public static void main(String[] args) {
        String s = "226";
        System.out.println(numDecodings(s));
    }
    public static int numDecodings(String s) {
        char[] arr = s.toCharArray();
        int[] dp = new int[arr.length + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        return numDecodingsDp(arr, 0, dp);
    }

    public static int numDecodingsDp(char[] arr, int i, int[] dp) {
        if (i >= arr.length) {
            return 1;
        }
        if (arr[i] == '0') {
            return 0;
        }
        if(dp[i]!=Integer.MAX_VALUE) {
            return dp[i];
        }
        int num = numDecodingsDp(arr, i + 1, dp);
        if ((i + 1 <= arr.length - 1)
                && ((arr[i] - '0') * 10 + arr[i + 1] - '0' <= 26)) {
            num += numDecodingsDp(arr, i + 2, dp);
        }
        dp[i] = num;
        return num;
    }
}